# 折半查找




def binary_search(arr,target):
    left = 0                         #左指针
    right = len(arr)-1               #右指针

    while left <= right:            #主体循环，循环前提：左指针要小于右指针

        mid = (left+right)//2       #找到中间指针位置

        if arr[mid] == target:      #如果中间指针正好为目标，则中间指针就为目标索引（条件1）

            return mid
        elif arr[mid] < target:     #目标值在中指针右侧情况                    （条件2）
            left = mid + 1
        else:                       #在左侧情况，即arr[mid] > target          （条件3）
            right = mid - 1
    return -1                       #三种情况都不满足则为查找失败，返回-1
#测试用例
test_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
print(binary_search(test_array, 10))